{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "yWabJ-GfTENP"
   },
   "source": [
    "<img src=\"https://raw.githubusercontent.com/Qiskit/qiskit-tutorials/master/images/qiskit-heading.png\" alt=\"Note: In order for images to show up in this jupyter notebook you need to select File => Trusted Notebook\" width=\"500 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implementation of Quantum Walks on Cycle Graph\n",
    "This notebook is based on the paper of  B L Douglas and J B Wang, \"Efficient quantum circuit implementation of quantum walks\", arXiv:0706.0304 [quant-ph].\n",
    "\n",
    "***\n",
    "### Contributors\n",
    "Jordan Kemp (University of Chicago), Shin Nishio (Keio University), Ryosuke Satoh (Keio University), Desiree Vogt-Lee (University of Queensland), and Tanisha Bassan (The  Knowledge Society)\n",
    "\n",
    "### Qiskit Package Versions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'qiskit': '0.10.3',\n",
       " 'qiskit-terra': '0.8.1',\n",
       " 'qiskit-ignis': '0.1.1',\n",
       " 'qiskit-aer': '0.2.1',\n",
       " 'qiskit-ibmq-provider': '0.2.2',\n",
       " 'qiskit-aqua': '0.5.1'}"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import qiskit\n",
    "qiskit.__qiskit_version__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "\n",
    "There are many different types of quantum walks: a walker can walk on n-dimensional space or any limited graphs. First we will talk about the concept and dynamics of the quantum random walk and then show the implementation of a quantum walk on cycle graph."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Random walk \n",
    "A random walk is a dynamical path with a randomly evolving time system. The figure below shows a simple type of random walk. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"../images/quantum_walk/random_walk.png\" alt=\"Note: In order for images to show up in this jupyter notebook you need to select File => Trusted Notebook\" width=\"500 px\" align=\"center\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The dynamics can be regarded as a simple algorithm:\n",
    "1. There is a $n$-dimensional space (in this case, one for simplicity) and a walker which starts at the point $x=0$\n",
    "2. The walker then takes a step either forwards (towards $+x$) or backwards (towards $-x$) \n",
    "\n",
    "In the second step, the choice is made randomly (eg. a coin-flip). We can call this the \"Coin Operator\". \n",
    "\n",
    "For this system: $p+q = 1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quantum Walk \n",
    "A quantum walk is the \"quantum version\" of a classical random walk. This means the coin function will be a Unitary gate ($U(2)$) which is non-random and reversible:\n",
    "\n",
    "$$p+q = U \\in U(2)$$\n",
    "\n",
    "In this notebook, we use a Hadamard gate for executing the coin function since it puts our qubits in a state of superposition, allowing for the  simulation of a coin based probability:\n",
    "\n",
    "$$H=\\frac{1}{\\sqrt{2}}\\left [{\\begin{array}{rr}1 & 1 \\\\ 1 & -1\\\\ \\end{array}}\\right]$$\n",
    "\n",
    "There are two kinds of random walks, continuous and discrete, and in this notebook we will use the discrete framework. In the discrete, unitary operations are made of coin and shift operators $U = SC$ which work in a state space.\n",
    "\n",
    "It is represented by an arbitrary undirected graph $G(V,E)$ where $V = {v_1, v_2, ..v_n}$ as nodes on the graph and $E = {(v_x, v_y) , ( v_i, v_j) …}$ as edges that combine different nodes together.\n",
    "\n",
    "The quantum walk extends into a position space where each node $v_i$ has a certain valency $d_i$ and is split into $d_i$ subnodes. The shifting operator then acts as $S (v_i, a_i) = (v_j, a_j)$ and with the coin operator, are unitary gates which combine the probability amplitudes with individual subnodes under each node.\n",
    "\n",
    "A unitary of $v_i$ with valency $d_i$ can be represented as $(d_i \\times d_i)$. The total state of system is defined by the Hilbert space \n",
    "\n",
    "$$H = H_c + H_p$$ \n",
    "\n",
    "Where $H_C$ is the coin Hilbert space and $H_P$ is the position Hilbert space. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Coin Operator \n",
    "The first operation in a quantum random walk is the coin operator. The operator works by performing an arbitrary unitary transformation in the coin space which creates a rotation similar to “coin-flip” in random walk. This is namely the Hadamard gate, which models a balanced unitary coin. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The coin register will continue interfering with its position state until it is measured, after all intermediate steps. The results are very different from random walks as it doesn’t converge to a Gaussian distribution, but rather evolves into an asymmetric probability distribution. This happens because the Hadamard coin operator treats each basis vectors, |↑> and |↓> , differently. \n",
    "\n",
    "The rightwards path interferes more destructively as it is multiplied by -1, however, the leftwards path undergoes more constructive interference and the system tends to take steps towards the left. To reach symmetric results, both base vectors will start in a superposition of states (between  |↑> and |↓>). Another way to reach symmetry is use a different coin operator which doesn’t bias the coin towards a certain base vector, such as the Y gate:\n",
    "\n",
    "$$Y=\\frac{1}{\\sqrt{2}}\\left [{\\begin{array}{rr}1 & i \\\\ i & 1\\\\ \\end{array}}\\right]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quantum Walk on the Cycle Graph\n",
    "\n",
    "The goal of this notebook is to conduct a quantum random walk on circular graph which can be efficiently and simply implemented on the quantum circuit. The graph has 8 nodes with 2 attached edges which act as the subnodes on the circuit. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"../images/quantum_walk/8_white.jpg\" alt=\"Note: In order for images to show up in this jupyter notebook you need to select File => Trusted Notebook\" width=\"350 px\" align=\"center\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The operations propagate systemically around the graph as each node is a seperate bit-string value in lexicographic order. For a 2n graph, n qubits are required to encode the problem and 1 ancilla qubit is required for the subnode (coin). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"../images/quantum_walk/whole_circuit.jpg\" alt=\"Note: In order for images to show up in this jupyter notebook you need to select File => Trusted Notebook\" width=\"700 px\" align=\"center\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above circuit shows the whole process of the quantum walk on a cycle graph with $2^3$ nodes. \n",
    "\n",
    "The gray rectangular frame outlines a set of coin operators and shift operators. \n",
    "\n",
    "In this circuit, q[0] to q[2] represent the state (position) of quantum walker, and q[3] represents the coin operator.\n",
    "\n",
    "In this style, a programmer can insert the initial position of walker as a 3-qubit state. For example, if the input is $110$, then the position is $6$ (see the earlier cycle graph). \n",
    "\n",
    "The coin operator decides whether the walker proceeds clockwise or counterclockwise.\n",
    "\n",
    "INC is a gate that increments the state of the walker which is equal to a clockwise rotation in the cycle graph. \n",
    "\n",
    "DEC is gate that decrements the state of the walker which is equal to a counterclockwise rotation in cycle graph.\n",
    "\n",
    "After repeatedly executing the coin operator and the shift operator, we can measure the qubits (excluding the ancilla coin qubit), and it is then possible to know the position of the walker."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## $n$-qubit Toffoli\n",
    "\n",
    "The Toffoli gate is a CCNOT(CCX) gate. By using the Toffoli gate, X gates executed on Q2 if Q0 and Q1 is equal to 1.\n",
    "\n",
    "In our quantum walk implementation, we need more connections to expand the quantum walk implementation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"../images/quantum_walk/toffoli.png\" alt=\"Note: In order for images to show up in this jupyter notebook you need to select File => Trusted Notebook\" align=\"center\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example, CCX can be written as in the below circuit by using only the available gate sets of the IBMQ devices.\n",
    "\n",
    "Therefore, for more than 4 qubits, we can implement many qubits of CX gate (\"C$N$X gate\") using this method. Reference shown [here](\"https://journals.aps.org/pra/abstract/10.1103/PhysRevA.52.3457\")."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"../images/quantum_walk/implement_toffoli.png\" alt=\"Note: In order for images to show up in this jupyter notebook you need to select File => Trusted Notebook\" align=\"center\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C$N$X can be represented using C($N-1$)X as shown."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cnx(qc, *qubits):\n",
    "    if len(qubits) >= 3:\n",
    "        last = qubits[-1]\n",
    "        # A matrix: (made up of a  and Y rotation, lemma4.3)\n",
    "        qc.crz(np.pi/2, qubits[-2], qubits[-1])\n",
    "        qc.cu3(np.pi/2, 0, 0, qubits[-2],qubits[-1])\n",
    "        \n",
    "        # Control not gate\n",
    "        cnx(qc,*qubits[:-2],qubits[-1])\n",
    "        \n",
    "        # B matrix (pposite angle)\n",
    "        qc.cu3(-np.pi/2, 0, 0, qubits[-2], qubits[-1])\n",
    "        \n",
    "        # Control\n",
    "        cnx(qc,*qubits[:-2],qubits[-1])\n",
    "        \n",
    "        # C matrix (final rotation)\n",
    "        qc.crz(-np.pi/2,qubits[-2],qubits[-1])\n",
    "    elif len(qubits)==3:\n",
    "        qc.ccx(*qubits)\n",
    "    elif len(qubits)==2:\n",
    "        qc.cx(*qubits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We then need to decide the number of qubits $n$ to represent the walker's state (the whole circuit requires $n+1$ qubits)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "lHI4G7fgT9Wn"
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from qiskit import IBMQ, QuantumCircuit, ClassicalRegister, QuantumRegister, execute\n",
    "from qiskit.tools.visualization import plot_histogram, plot_state_city\n",
    "\n",
    "n=3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 85
    },
    "colab_type": "code",
    "id": "kLSxVQxerGyo",
    "outputId": "b319f1d1-b5aa-4113-e12b-eecbf993a362"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<IBMQBackend('ibmqx4') from IBMQ()>,\n",
       " <IBMQBackend('ibmqx2') from IBMQ()>,\n",
       " <IBMQBackend('ibmq_16_melbourne') from IBMQ()>,\n",
       " <IBMQSimulator('ibmq_qasm_simulator') from IBMQ()>]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IBMQ.load_accounts()\n",
    "IBMQ.backends()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We then need to execute the increment and decrement gate in order for the shift operator to walk, including the C$N$X gates which changes the position of the walker based on the coin operator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "ysx7VXO2a95V"
   },
   "outputs": [],
   "source": [
    "def increment_gate(qwc, q, subnode):\n",
    "  \n",
    "  cnx(qwc, subnode[0], q[2], q[1], q[0])\n",
    "  cnx(qwc, subnode[0], q[2], q[1])\n",
    "  cnx(qwc, subnode[0], q[2])\n",
    "  qwc.barrier()\n",
    "  return qwc\n",
    "\n",
    "def decrement_gate(qwc, q, subnode):\n",
    "  \n",
    "  qwc.x(subnode[0])\n",
    "  qwc.x(q[2])\n",
    "  qwc.x(q[1])\n",
    "  cnx(qwc, subnode[0], q[2], q[1], q[0])\n",
    "  qwc.x(q[1])\n",
    "  cnx(qwc, subnode[0], q[2], q[1])\n",
    "  qwc.x(q[2])\n",
    "  cnx(qwc, subnode[0], q[2])\n",
    "  qwc.x(subnode[0])\n",
    "  return qwc\n",
    "  \n",
    "def ibmsim(circ):\n",
    "  ibmqBE = IBMQ.get_backend('ibmq_qasm_simulator')\n",
    "  return execute(circ,ibmqBE, shots=1000).result().get_counts(circ)  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rerun the coin and shift operators for n number of steps (in this case 15)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 408
    },
    "colab_type": "code",
    "id": "PUUoi5T69zvX",
    "outputId": "11b916d3-4cc9-40d2-9017-dc072de02630"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'0 111': 491, '0 100': 509}\n"
     ]
    }
   ],
   "source": [
    "qnodes = QuantumRegister(n,'qc')\n",
    "qsubnodes = QuantumRegister(1,'qanc')\n",
    "csubnodes = ClassicalRegister(1,'canc')\n",
    "cnodes = ClassicalRegister(n,'cr')\n",
    "\n",
    "qwc = QuantumCircuit(qnodes, qsubnodes, cnodes, csubnodes)\n",
    "\n",
    "\n",
    "def runQWC(qwc, times):\n",
    "    for i in range(times):\n",
    "        qwc.h(qsubnodes[0])\n",
    "        increment_gate(qwc, qnodes, qsubnodes[0])\n",
    "        decrement_gate(qwc,qnodes,qsubnodes[0])\n",
    "        qwc.measure(qnodes, cnodes)\n",
    "\n",
    "    return qwc\n",
    "\n",
    "import matplotlib as mpl\n",
    "\n",
    "step = 1\n",
    "qwc = runQWC(qwc, step)\n",
    "qwc.draw(output=\"mpl\")\n",
    "result = ibmsim(qwc)\n",
    "\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "LprBkgB9AGVr"
   },
   "outputs": [],
   "source": [
    "def runQWC(qwc, times):\n",
    "    for i in range(times):\n",
    "        qwc.h(qsubnodes[0])\n",
    "        increment_gate(qwc, qnodes, qsubnodes[0])\n",
    "        decrement_gate(qwc,qnodes,qsubnodes[0])\n",
    "        qwc.measure(qnodes, cnodes)\n",
    "\n",
    "    return qwc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first qubit which is always 0, is the coin qubit.\n",
    "The second to fourth, is the position of the walker (binary).\n",
    "The distribution can be seen using plot_histogram."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAc0AAAFUCAYAAABGLGeWAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjAsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+17YcXAAAgAElEQVR4nO3de5zVdb3v8dfH4eoFZZCNMykqQoRoNEoXS9EstdzbfSo9ufcxtdrm6aZt7WYd21rbTedQtrV27dK2eSszjSxrk0RQ5CVNRBJFwlCIi4iIeOEyMHzOH2tBwzgz/BYs1gwzr+fjsR6s9ft9f9/5LPDre3637y8yE0mStH17dHUBkiTtLgxNSZIKMjQlSSrI0JQkqSBDU5KkggxNSZIKMjQlSSqo5qEZER+NiCcjYn1EzIqI47bTvl9EfKm8zYaIWBwRF7Zpc3pEPFZe/1hEvHvXfgtJUm9U09CMiDOBq4GJQBNwLzAlIoZ3stkPgXcA5wOjgf8J/LFVn8cAtwLfB15X/vO2iHjjrvgOkqTeK2o5I1BE3A/8MTM/1GrZAuD2zPxcO+1PBm4DDsvMZzvo81agPjNParVsGrAyM/+x2t9BktR71WxPMyL6AUcDU9usmgq8uYPN3gX8Abg4IpZExIKI+HpE7N2qzTHt9HlXJ31KkrRD+tTwZ+0P1AEr2ixfAby9g21GAMcCG4DTgf2AbwCNwBnlNgd00OcB7XUYEedTOtTLwIEDjz7ooIMA6Nu3L3vssQcbNmwAoK6ujn79+rFu3bqt2+65556sX7+ezZs3AzBgwAA2bdrEpk2btvYRETQ3N7fbR0QwcOBA1q1bx5Y9/LZ99OvXD2CbPvr27cv69es77WPjxo20tLS020efPn3o06dPp30MHDiQ5ubmbfrITDZu3NhuH3vssQcDBgxg7dq1W/9+2vbRv39/Nm/evLWPtn/H7fXR9u94e3347+S/k/9O/jtV+9/p0UcffTYzh9KOWobmjtgDSOB/ZeYagIj4OHBXRAzLzLZhuV2ZeQ1wDUBTU1NOnz69mvVKknZz9fX1izpaV8sLgZ4FWoBhbZYPA57uYJvlwNItgVk2r/znlouHnq6wT0mSdkjNQjMzm4FZwEltVp1E6Sra9twDNLY5h/nq8p9bfhO4r8I+JUnaIbW+T/NrwPsj4ryIGBMRV1M6P/ltgIi4MSJubNX+B8Aq4HsRMTYi3kLplpXbM/OZcpurgRMj4pKIeE1EfA54K3BVrb6UJKl3qOk5zcy8NSKGAJcCDcBc4NTM3LLXOLxN+5ci4u2ULv75A7AauAO4pFWbeyPiH4ArgC8BfwbOzMz7d/X3kST1LjW9T7O78UIgSVJb9fX1szJzfHvrnHtWkqSCDE1JkgoyNCVJKsjQlCSpIENTkqSCDE1JkgoyNCVJKsjQlCSpIENTkqSCDE1JkgoyNCVJKsjQlCSpIENTkqSCDE1JkgoyNCVJKsjQlCSpIENTkqSCDE1J2k1MmzaNN7zhDRx99NFcddVVr1j/gx/8gFGjRjFhwgQmTJjAjTfeuHXdLbfcwvjx4xk/fjy33HLL1uVXXHEFRxxxBAcddFBNvsPuztDs5bY3CLf42c9+Rn19PbNnzwagubmZj33sY7zlLW/huOOO4+67797advLkyRx77LEcc8wxXH755bv6K0i9QktLC5/5zGf40Y9+xH333cePf/xjHn/88Ve0e/e7383MmTOZOXMm55xzDgCrV69m0qRJ/OpXv2LatGlMmjSJ559/HoBTTjmFadOm1fS77M4MzV6s6CB88cUX+c53vsPRRx+9ddmW32DvueceJk+ezBe+8AU2b97Mc889x2WXXcYdd9zBfffdxzPPPMNvf/vbmn0nqaeaNWsWhx56KIcccgj9+vXjPe95D1OmTCm07fTp0znhhBMYPHgw++23HyeccAK//vWvAXj961/PAQccsCtL71EMzV6s6CCcOHEin/jEJxgwYMDWZfPnz2fChAkADB06lH333ZfZs2fz1FNPcdhhh7H//vsDcPzxx3PnnXfW5gtJPdjy5ct51atetfVzY2Mjy5cvf0W7O++8k2OPPZZzzz2XJUuWALBs2bJXbLts2bJdX3QPZGj2YkUG4Zw5c1i6dCknn3zyNsvHjh3LlClT2LRpE4sWLeLhhx9m6dKljBgxggULFrB48WI2bdrEL37xC5YuXVqT7yP1du94xzt4+OGHufvuu3nrW9/Kxz72sa4uqccxNNWhzZs3c+mll3LFFVe8Yt373vc+GhsbOfHEE/n85z/PG97wBurq6thvv/248sor+eAHP8ipp57K8OHDqaur64LqpZ6loaFhm19Aly1bRkNDwzZt6uvr6d+/PwBnn302Dz/8MFD6hbjtto2NjTWouucxNHux7Q3Cl156iXnz5nHaaacxbtw4HnzwQc466yxmz55Nnz59mDhxIjNnzuT73/8+a9as4bDDDgNKv+1OmzaNqVOnMnLkyK3LJe24o446ioULF7Jo0SKam5uZPHky73jHO7Zp8/TTT299P2XKFF796lcDcOKJJzJjxgyef/55nn/+eWbMmMGJJ55Y0/p7ij5dXYC6TutB2NDQwOTJk7nmmmu2rh80aBBPPPHE1s+nnXYaX/rSl2hqamLt2rVkJnvttRczZsygT58+vOY1rwFg5cqVDB06lOeff57rrruO6667rubfTepp+vTpw6RJkzjjjDNoaWnhrLPOYsyYMUycOJGmpibe+c53cs011zBlyhT69OnD4MGD+eY3vwnA4MGD+dSnPsXb3vY2AD796U8zePBgAC677DJuv/121q5dy9ixYzn77LO55JJLuux7dneRmV1dQ5dpamrK6dOnd3UZXepXv/oVn//857cOwk9+8pPbDMLWWofm4sWLOeOMM4gIGhsb+frXv771Pq/zzjuPuXPnAqXBefrpp9f8e0nSjqqvr5+VmePbW2do9vLQlCRtq7PQ9JymJEkFGZqSJBVkaEqSVJChKUlSQYamJEkFGZqSJBVkaEqSVJChKUlSQYamJEkFGZqSJBVkaEqSVJBPOZHU63zmhsFdXYJ2gUnnrt7lP8PQrAIHYM9UiwEoaffi4VlJkgoyNCVJKsjQlCSpIENTkqSCDE1JkgoyNCVJKsjQlCSpIENTkqSCDE1JkgoyNCVJKsjQlCSpIENTkqSCDE1JkgoyNCVJKsjQlCSpIENTkqSCDE1JkgqqeWhGxEcj4smIWB8RsyLiuILbHRsRmyJibpvl74+IbOc1YNd8A0lSb1XT0IyIM4GrgYlAE3AvMCUihm9nu8HAjcCvO2iyFmho/crM9dWqW5IkqP2e5sXA9Zl5bWbOy8wLgOXAR7az3X8BNwD3dbA+M/Pp1q8q1ixJElDD0IyIfsDRwNQ2q6YCb+5ku48Cw4ArOul+YEQsioglEfHziGja6YIlSWqjTw1/1v5AHbCizfIVwNvb2yAijgQuA96UmS0R0V6z+cAHgTnAPsAngHsiYlxmLminz/OB8wEaGhp46KGHAGhsbGTPPffkiSeeAGDfffdlxIgRzJ49G4C6ujrGjRvH/PnzefnllwEYM2YMzz33HDC48F+Cdh/z5s1j3bp1ABx++OGsXLmSlStXAnDwwQcTETz11FMADBkyhIaGBubOLZ1y79+/P2PHjuXRRx9lw4YNABxxxBEsX76cVatWAXDIIYeQmSxatAiAoUOHMnToUB577DEABg4cyJgxY3jkkUfYuHEjAOPGjWPx4sWsXr0agBEjRtDc3MySJUsAGDZsGPX19cybNw+Avfbai9GjRzNnzhxaWloAaGpqYuHChaxZswaAkSNHsnbtWpYtWwaUxsWgQYOYP38+APvssw+jRo1i9uzZZCYRQVNTEwsWLODFF18EYPTo0bzwwgssX74c2LnxtGJF6X8RBx54IP369WPhwoUADB48mOHDhzNnzhwA+vbty5FHHrlD/07qmVatWlWV8dSZyMxd+BVa/aCIRmApcHxmzmy1/F+AszJzdJv2/YHZwJcz86byssuBMzLziE5+Th3wMDAjMy/srKampqacPn36Dn6jv/rMDYZmTzTp3NVdXYJ2Ecdsz1StMVtfXz8rM8e3t66We5rPAi2UDrW2Ngxo7xxkAzAG+F5EfK+8bA8gImITcGpmtj3US3mP9EFgVNUqlySJGp7TzMxmYBZwUptVJ1G6iratpcCRwOtavb4NPFF+3942ROkY7mspXWAkSVLV1HJPE+BrwE0R8QBwD/BhoJFSGBIRNwJk5jmZuRFoe0/mM8CGzJzbatllwO+BBcAg4EJKobm9K3IlSapITUMzM2+NiCHApZQOv86ldJh1UblJp/drdmA/4BrgAGANpfOgEzLzgSqULEnSVrXe0yQzvwV8q4N1J2xn28uBy9ssuwi4qDrVSZLUMeeelSSpIENTkqSCDE1JkgoyNCVJKsjQlCSpIENTkqSCDE1JkgoyNCVJKsjQlCSpIENTkqSCDE1JkgoyNCVJKsjQlCSpIENTkqSCDE1JkgoyNCVJKsjQlCSpIENTkqSCDE1JkgoyNCVJKsjQlCSpoIpCMyLeGxEnt/r8LxGxJCLuioiG6pcnSVL3Ueme5uVb3kTEUcDnga8DfYErq1eWJEndT58K2x8MzC+/fzdwR2ZOioipwF1VrUySpG6m0j3N9cA+5fdvA6aV369ptVySpB6p0j3N3wFXRsTdwHjgjPLyVwN/qWZhkiR1N5XuaX4caKYUlh/OzGXl5e/Ew7OSpB6uoj3NzFwCnNbO8n+uWkWSJHVTFd+nGREDIuKMiPhsROxXXnZYRNRXvzxJkrqPivY0I2IkpYt/9gb2A24Dngc+Uv58XrULlCSpu6h0T/MqYCowDFjXavnPgLdWqyhJkrqjSq+efTPwpsxsiYjWyxcDjVWrSpKkbmhH5p7t286y4ZTu1ZQkqceqNDSnAhe3+pwRMQj4IvCLqlUlSVI3VOnh2YuBGRExHxgA3AqMBFYA761ybZIkdSuV3qe5LCJeB/wjcBSlPdVrgO9n5rpON5YkaTdX6Z4m5XC8rvySJKnX2G5oRsR7gDszc2P5fYcyc3LVKpMkqZspsqd5O3AA8Ez5fUcSqKtGUZIkdUfbDc3M3KO995Ik9TYVhWBETIiIVwRtRNRFxITqlSVJUvdT6Z7jDKC9idn3K6+TJKnHqjQ0g9K5y7aGAC/vfDmSJHVfhW45iYifld8mcHNEbGi1ug44Ari3yrVJktStFL1Pc1X5zwBWs+0TTpqBu4Frq1iXJEndTqHQzMwPAETEU8BXM9NDsZKkXqfSafS+uKsKkSSpuysyI9AfgeMzc3VEPEL7FwIBkJmvrWZxkiR1J0X2NH8MbLnwp7MZgSRJ6tGKzAj0xfbeS5LU2zgtniRJBRU5p9npeczWPKcpSerJij7lRJKkXq+ic5qSJPVmntOUJKkg79OUJKkg79OUJKmgmt+nGREfBT4NNACPAv+cmb/roO3xwJeB0cCewCLgu5n51TbtTgf+FTgM+DPwfzLzJztbqyRJre3QOc2IOCwi/q78OqyC7c4ErgYmAk2UHic2JSKGd7DJS8DXgQnA4cAVwBfLwbulz2OAW4HvA68r/3lbRLyx8m8mSVLHKgrNiBgSEXcAC4A7yq8/RcRPI2JIgS4uBq7PzGszc15mXgAsBz7SXuPMnJWZP8zMRzPzycy8GbgLOK5Vs38GZmTmv5X7/DfgN+XlkiRVTaV7mt8FRlIKrQHl1wTgULbzPM2I6AccDUxts2oq8OYiPzwimsptf9tq8THt9HlX0T4lSSqqokeDAacAb8vM+1otuyci/jcwbTvb7g/UASvaLF8BvL2zDSNiCTCUUr1fzMxvt1p9QAd9HtBBX+cD5wM0NDTw0EMPAdDY2Miee+7JE088AcC+++7LiBEjmD17NgB1dXWMGzeO+fPn8/LLpceJjhkzhueeew4Y3Fn52k3NmzePdetKz1s//PDDWblyJStXrgTg4IMPJiJ46qmnABgyZAgNDQ3MnTsXgP79+zN27FgeffRRNmwoXUd3xBFHsHz5clatKj3T/ZBDDiEzWbRoEQBDhw5l6NChPPbYYwAMHDiQMWPG8Mgjj7Bx40YAxo0bx+LFi1m9ejUAI0aMoLm5mSVLlgAwbNgw6uvrmTdvHgB77bUXo0ePZs6cObS0tADQ1NTEwoULWbNmDQAjR45k7dq1LFu2DCiNi0GDBjF//nwA9tlnH0aNGsXs2bPJTCKCpqYmFixYwIsvvgjA6NGjeeGFF1i+fDmwc+NpxYrScD7wwAPp168fCxcuBGDw4MEMHz6cOXPmANC3b1+OPPLIHfp3Us+0atWqqoynzkRmoRnySo0jFgGnZeYf2ywfB9yZmR2dmyQiGoGllG5fmdlq+b8AZ2Xm6E62PRTYG3gT8P+AT2TmTeV1zcB5mXljq/bnANdmZv/Ovk9TU1NOnz69syaFfOYGQ7MnmnTu6q4uQbuIY7ZnqtaYra+vn5WZ49tbV+me5peAqyLi7MxcChARrwKuLK/rzLNACzCszfJhwNOdbZiZT5bfPhIRw4DLgZvKy57ekT4lSarUjkzYfijwVEQsLX9+FbAe+BtK5zzblZnNETELOAm4rdWqkyjdC1rUHkDrPcj7yn18pU2f91bQpyRJ21XrCdu/BtwUEQ8A9wAfBhqBbwNExI0AmXlO+fMFwJPA/PL2E4BPAd9q1efVwMyIuITS1bzvBt4KHFvFuiVJqu2E7Zl5a/nWlEspTW4wFzg1MxeVm7Q9J1pH6RzmIcAmShMXXEI5ZMt93hsR/0DpHs4vlducmZn3V6tuSZKg8nOaOy0zv8W2e4qt153Q5vNVwFUF+rwdp/iTJO1ilU5u0C8ivhgRf4qI9RHR0vq1q4qUJKk7qHRyg38FzqV0texmSnPIfhNYBXy0k+0kSdrtVRqa7wU+nJnfoXT7yE8z80LgMkpXrEqS1GNVGprDgMfK718C9iu//yVwcrWKkiSpO6o0NBdTukUE4AlK0+pBaf7XddUqSpKk7qjS0PwJ8Lby+6spPabrSeB6OpnYQJKknqCiW04y83Ot3t9enkj9zcCfMvPn1S5OkqTuZKfu08zM3wO/r1ItkiR1a5UeniUijoqIGyPiwfLrpog4alcUJ0lSd1Lp5AZnAX+gNAXef5dfw4AHIuJ91S9PkqTuo9LDs/8GfCEzJ7ZeGBGfozT3683VKkySpO6m0sOzQ4EftbP8NkqPBpMkqceqNDRnACe0s/wE4Lc7W4wkSd1ZkYdQv6fVxynAlyNiPH+9avZNwHuAy6tenSRJ3ciOPoT6/PKrtW/QwSO/JEnqCYo8hLri21IkSeqJDERJkgrakckN/jYiZkbEsxGxMiJ+GxGn7oriJEnqTiqd3OA8SpO2/xn4LHAJ8CTwk4j4YPXLkySp+6h0coPPAhdn5n+0WvZfETGLUoBeV7XKJEnqZio9PDuc0gOn25oCHLzz5UiS1H3tyEOoT2pn+cnAop0vR5Kk7qvSw7NfBb5RfqrJveVlbwHOBi6oZmGSJHU3lT6E+jsR8QzwSUqzAAHMA96bmT+tdnGSJHUnhUMzIvpQOgw7MzN/sutKkiSpeyp8TjMzNwGTgX12XTmSJHVflV4INAcYuSsKkSSpu6s0NC8HroyId0XEQRFR3/q1C+qTJKnbqPTq2V+U/5wMZKvlUf5cV42iJEnqjioNzbfukiokSdoNFArNiNgT+ArwLqAvMA24MDOf3YW1SZLUrRQ9p/lF4P2UDs/eQmlWoP/cRTVJktQtFT08+x7gnzLzhwAR8X3gnoioy8yWXVadJEndSNE9zYOA3235kJkPAJuAxl1RlCRJ3VHR0KwDmtss20TlFxJJkrTbKhp6AdwcERtaLRsAXBsRa7csyMy/r2ZxkiR1J0VD84Z2lt1czUIkSeruCoVmZn5gVxciSVJ3V+k0epIk9VqGpiRJBRmakiQVZGhKklSQoSlJUkGGpiRJBRmakiQVZGhKklSQoSlJUkGGpiRJBRmakiQVZGhKklSQoSlJUkGGpiRJBRmakiQVZGhKklSQoSlJUkGGpiRJBRmakiQVVPPQjIiPRsSTEbE+ImZFxHGdtG2IiB9ExOMR0RIR17fT5v0Rke28BuzSLyJJ6nVqGpoRcSZwNTARaALuBaZExPAONukPPAv8X+D+TrpeCzS0fmXm+mrVLUkS1H5P82Lg+sy8NjPnZeYFwHLgI+01zsynMvPCzLweeK6TfjMzn279qn7pkqTermahGRH9gKOBqW1WTQXevJPdD4yIRRGxJCJ+HhFNO9mfJEmv0KeGP2t/oA5Y0Wb5CuDtO9HvfOCDwBxgH+ATwD0RMS4zF7RtHBHnA+cDNDQ08NBDDwHQ2NjInnvuyRNPPAHAvvvuy4gRI5g9ezYAdXV1jBs3jvnz5/Pyyy8DMGbMGJ577jlg8E6Ur+5q3rx5rFu3DoDDDz+clStXsnLlSgAOPvhgIoKnnnoKgCFDhtDQ0MDcuXMB6N+/P2PHjuXRRx9lw4YNABxxxBEsX76cVatWAXDIIYeQmSxatAiAoUOHMnToUB577DEABg4cyJgxY3jkkUfYuHEjAOPGjWPx4sWsXr0agBEjRtDc3MySJUsAGDZsGPX19cybNw+Avfbai9GjRzNnzhxaWloAaGpqYuHChaxZswaAkSNHsnbtWpYtWwaUxsWgQYOYP38+APvssw+jRo1i9uzZZCYRQVNTEwsWLODFF18EYPTo0bzwwgssX74c2LnxtGJF6X8RBx54IP369WPhwoUADB48mOHDhzNnzhwA+vbty5FHHrlD/07qmVatWlWV8dSZyMxd+BVa/aCIRmApcHxmzmy1/F+AszJz9Ha2/znwbGa+fzvt6oCHgRmZeWFnbZuamnL69OkFv0HHPnODodkTTTp3dVeXoF3EMdszVWvM1tfXz8rM8e2tq+U5zWeBFmBYm+XDgKqdg8zMFuBBYFS1+pQkCWoYmpnZDMwCTmqz6iRKV9FWRUQE8FpKFxhJklQ1tTynCfA14KaIeAC4B/gw0Ah8GyAibgTIzHO2bBARryu/HQRsLn9uzszHyusvA34PLCi3uZBSaLZ7Ra4kSTuqpqGZmbdGxBDgUkr3U84FTs3MReUm7d2vObvN59OARcAh5c/7AdcABwBryu0nZOYD1a1ektTb1XpPk8z8FvCtDtad0M6y2E5/FwEXVaU4SZI64dyzkiQVZGhKklSQoSlJUkGGpiRJBRmakiQVZGhKklSQoSlJUkGGpiRJBRmakiQVZGhKklSQoSlJUkGGpiRJBRmakiQVZGhKklSQoSlJUkGGpiRJBRmakiQVZGhKklSQoSlJUkGGpiRJBRmakiQVZGhKklSQoSlJUkGGpiRJBRmakiQVZGhKklSQoSlJUkGGpiRJBRmakiQVZGhKklSQoSlJUkGGpiRJBRmakiQVZGhKklSQoSlJUkGGpiRJBRmakiQVZGhKklSQoSlJUkGGpiRJBRmakiQVZGhKklSQoSlJUkGGpiRJBRmakiQVZGhKklSQoSlJUkGGpiRJBRmakiQVZGhKklSQoSlJUkGGpiRJBRmakiQVZGhKklSQoSlJUkGGpiRJBdU8NCPioxHxZESsj4hZEXHcdtofX263PiIWRsSHd7ZPSZJ2RE1DMyLOBK4GJgJNwL3AlIgY3kH7Q4H/LrdrAr4MfCMiTt/RPiVJ2lG13tO8GLg+M6/NzHmZeQGwHPhIB+0/DCzLzAvK7a8FbgA+tRN9SpK0Q2oWmhHRDzgamNpm1VTgzR1sdkw77e8CxkdE3x3sU5KkHVLLPc39gTpgRZvlK4ADOtjmgA7a9yn3tyN9SpK0Q/p0dQG1FhHnA+eXP75UX18/vyvr2Q3tDzzb1UXUwncv6uoKpKpwzFbu4I5W1DI0nwVagGFtlg8Dnu5gm6c7aL+p3F9U2mdmXgNcU7hqbSMiHszM8V1dh6RiHLPVVbPDs5nZDMwCTmqz6iRKV7y2574O2j+YmRt3sE9JknZIrQ/Pfg24KSIeAO6hdHVsI/BtgIi4ESAzzym3/zbw8Yi4CvgO8Bbg/cA/Fu1TkqRqqWloZuatETEEuBRoAOYCp2bmonKT4W3aPxkRpwL/TukWkmXAhZn54wr6VHV5aFvavThmqygys6trkCRpt+Dcs5IkFWRoSpJUkKEpSVJBhqYqEhH9ylMYviYiBnd1PZJUS14IpMIiYgLwaeBY4AlgFfAn4E7gN5m5sQvLk9RG+c6CNZm5qatr6SkMTRUSEftRup3nt8AdwGHAocBoYAAwDfjXzNzQZUVK2ioi9gH+C/gNcD+wMDNXt9PuVZm5tMbl7bZ63dyz2mEfApYC5275rTUiAngdcDpwATAiIj5gcErdwj8BZwBvB9YB0yNiCvAQ8JfMfLm8J3pTRPxTZj7ZhbXuNgxNFVVP6TmlARARdZnZAswGZkfEbyjdRD0a+GNXFSlpq2OArwBfBd4FnEfpF9zFwC8j4pfAG4EmA7M4LwRSUb8Ajgc+sCUwo6SuvP5u4CV8jqnU5SJiAPAw8HJmrszMazPzjcAY4EfA3wK3AJcB3+q6Snc/ntNUIRHRF5hE6bFqPwX+A/h9Zm6OiP6U9jDvB8Zm5sKuq1QSQEQcCAzIzCcioh+wKTM3t1r/XuCHwPDMXNJVde5uPDyr7YqIKF8Ze1FE3AN8Fvgd8Jfy5yHAq4EfGphS99A6CMtPhCIi9qC0s9QCHA48bWBWxj1NFRIRA4GNrS4CeiNwCnAc8Bf+etvJK67Ok1Rb5XCk9Z5lm/UBXAysyMyba1nb7s7QVKciYjilx62NAg4AlgA3ZOYvW7XZclGQpG6mfKToFf+jj4i9MvPlrqhpd2ZoqlMRcT9QR2kSg6eB11J6rukK4JvANZm5JiL26Oi3Wkm1ExEXAXOARzJzZavlAdBegKo4z2mqQxFxNjAUeH1mripf8LMf8BpKl7CfTemK2f80MKWuV76450rgD8DjEXEfMAuYl5kvldvsBUwEJjmpQeXc01SHIuJK4KDMfG876/YGLgE+DrwpMx+vdX2SthURNwF7U7qS/RTgIEpHhR4C7gMepDQhyXWZuXdX1bk7MzTVoYh4J/Bj4JzMvL2d9f2B6WqPS3kAAAN9SURBVMD3MvO7ta5P0l+Vbyv5LrA4My8tLzsaeC/wNmAQpTmjxwEzMvN9XVXr7szQVIfKoXg1MB64GfgVpQH5Ynl9A/A4cEpm/r7LCpVEeaKRI4G9M/PuthcARcQpwLnAPwDjM/OhLip1t2ZoqlMRcQhwKXAm8DwwFfgzcCCl2UUGZOYxXVWfpG21viivzX2ZRMT7gS9nZkMXlrhbMzRVSHli5w8B/wPoR+kCoPspXQTkvJVSF+vo1pJW6/sCt1K6N/MjtausZzE01aHyJep9gM2t78OMiKHAS5m5rsuKk/QK5TEbnUxqMAhozsz1ta2s5zA09QoR8RZgbmauabWsD6X7NZu9z0vqXjoYs50GqHaMoaltRMQxlB4yPYPSZeozgVnluWe3tBlI6UKC33VNlZK2KDhmB1C639oxu5MMTW0jIq4BTqY0+A4ENgALKJ2/nJmZ8yKiidL9Xnt7iFbqWo7Z2jI0tY2IuIvSE0yuBI4CTqV0y0k9sIbSA6ZfT2ny9hO7qk5JJY7Z2nIaPW1VPoRzM6XbSNYB9wD3RMS+wAnASZQG41uA07qqTkkljtnac09T2yhfPNA3M5vLF/+0tLlB+kOU5qwc3GVFStrKMVtbhqYK2XLDdETMANZn5ju7uiZJHXPM7hqGpioSEacCf87M+V1di6Ttc8xWl6EpSVJBe3R1Adq9bHmQraTdg2O2utzT1CuUB9kerafOk9R9OWZrxz1NbRURoyLib7Jky1MR/C1V6qYcs7XnnmYvFxF/A5wNXASsBDYBy4HbgMmZ+XIXliepDcds1zI0e7mIuB4YC9wJPEdpFpEm4DXAEuArmTm1ywqUtA3HbNcyNHux8mGcF4FTM3Nmq2UHAm+i9PzMg4EzM/PhLitUEuCY7Q48p9m7HQ48CTRvWVA+N/KXzLwN+DtKA/TMLqpP0rYcs13M0OzdFgLPAP9evqBgm/8eMrMZuAFwJhGpe3DMdjFDsxcrT/D8f4CBwI3AORFxUETsDRARewLHA3O7rkpJWzhmu57nNEVEHAF8Afh74GXgPkpX5b2d0lV552XmI11XoaTWHLNdx9DUVuVL2f8WeBewntJvq7dl5uNdWpikdjlma8/QVLu2PCGhq+uQVIxjtjYMTUmSCvJCIEmSCjI0JUkqyNCUJKkgQ1OSpIIMTUmSCjI0JUkqyNCUJKmg/w9D3m8G7sm2HwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 504x360 with 1 Axes>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result = ibmsim(qwc)\n",
    "plot_histogram(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Results\n",
    "\n",
    "The following animation is what the quantum walk looks like over its 19 iterations. The size of each node represents probability of the quantum walker existing in that position. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"../images/quantum_walk/fast.gif\" alt=\"Note: In order for images to show up in this jupyter notebook you need to select File => Trusted Notebook\" align=\"center\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Required Resources\n",
    "\n",
    "In this  algorithm, we needed $n+1$ qubits for a cycle graph with $2^n$ nodes. As you can see in the following graph, the time complexity increases linearly. This is the result of relation between execution time on 'qasm_simulator' and the number of steps."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"../images/quantum_walk/executiontime.png\" alt=\"Note: In order for images to show up in this jupyter notebook you need to select File => Trusted Notebook\" align=\"center\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Discussion about Future Work and Applications\n",
    "_Expansion of number of nodes on graph_ \n",
    "\n",
    "The walk implemented in this project required 3 qubits for 8 nodes plus an additional 1 qubit for the coin operator. The total time for iterating through coin and shift operator was 16 seconds for 100 flips. \n",
    "\n",
    "An example of a real world problem that can be solved using quantum random walks is the mapping of enzymes to understand their evolution when in contact with mutagens. This problem only requires 33 nodes which can be mapped out on 7 qubit circuit. This increase in qubits would increase the total time to 49 seconds for 100 flips. This is a scalable model which can continue to grow to map more complex graphs to problems. \n",
    "\n",
    "The time complexity for the quantum simulator approximately follows $({\\frac{m+1}{n+1}})^2$ if the number of nodes becomes $2^m$ from $2^n$. This value is based on number of qubits and is roughly estimated. \n",
    "\n",
    "## Conclusion\n",
    "In this notebook we showed the basics of the quantum random walk and its implementation on a cyclic quantum circuit.\n",
    "\n",
    "The implemented algorithm requires $n+1$ qubits for any cycle graph with $2^n$ nodes. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "quantum_walk.ipynb",
   "provenance": [],
   "version": "0.3.2"
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
